package top.minuy.structure.graph.path.weighted;

import top.minuy.structure.graph.representations.WeightedEdge;
import top.minuy.structure.graph.representations.table.WeightedGraph;

/**
 * 带权图最短路径算法
 *
 * @author Minuy
 * @time 19:49
 * @date 2021/11/25
 */
public class Dijkstra {
    private WeightedGraph g;
    private int[] dis;
    private boolean[] isVisited;

    public Dijkstra(WeightedGraph g, int s) {
        this.g = g;

        g.validateVertex(s);

        dis = new int[g.V()];
        for (int i = 0; i < dis.length; i++) {
            dis[i] = Integer.MAX_VALUE;
        }

        isVisited = new boolean[g.V()];

        dis[s] = 0;

        while (true) {
            // 找到图中路径最短的那个顶点
            int minV = -1, minDis = Integer.MAX_VALUE;
            for (int v = 0; v < g.V(); v++) {
                if (!isVisited[v] && dis[v] < minDis) {
                    minDis = dis[v];
                    minV = v;
                }
            }

            // 如果找不到了，就可以退出了
            if (minV == -1) {
                break;
            }

            isVisited[minV] = true;
            for (int v : g.adj(minV)) {
                if(!isVisited[v]) {
                    int newDis = dis[minV] + g.getWeight(v, minV);
                    if (newDis < dis[v]) {
                        dis[v] = newDis;
                    }
                }
            }

        }

        {/*之前自己实现的版本，有BUG*/
            // WeightedEdge minEdge = new WeightedEdge(-1, -1, Integer.MAX_VALUE);
//        for (; cnt < g.V(); cnt++) {
//
//            // 设置当前顶点为确定的
//            isVisited[v] = true;
//
//            // 更新其相邻的点的路径长度
//            for (int w : g.adj(v)) {
//                if (!isVisited[w]) {
//                    dis[w] = dis[v] + g.getWeight(w, v);
//                }
//            }

            // 找出其相邻的最小权边，
//            for (int w : g.adj(v)) {
//                if (!isVisited[w]) {
//                    WeightedEdge edge = new WeightedEdge(v, w, g.getWeight(v, w));
//                    minEdge = edge.compareTo(minEdge) > 0 ? minEdge : edge;
//                }
//            }
            // 不能这么找，说不定这个周围全是访问过的
//            /*
//            .  以下，从1开始
//            .        4
//            .     1 -- 3
//            .   3/|   |
//            .  0 2|  6|
//            .  1\ |   |
//            .    2 -- 4
//            .      8
//             */
//            v = minEdge.v != v ? minEdge.v : minEdge.w;
//        }
        }

    }

    public boolean isConnectedTo(int t){
        g.validateVertex(t);
        return isVisited[t];
    }

    public int disTo(int t){
        g.validateVertex(t);
        return dis[t];
    }
}
